Classification is a crucial process in data mining, data science, machine learning, and the applications of natural language processing. Classification methods distinguish the correlation between the data and the output classes. In single-Label classification (SLC), each input sample is associated with only one class Label. In certain real-world applications, data instances may be assigned to more than one class. The type of classification which is required in such applications is known as multi-Label classification (MLC). In MLC, each sample of data is associated with a set of Labels. Due to the presence of multiple class Labels, the SLC learning process is not applicable to MLC tasks. Many solutions to the multi-Label classification problem have been proposed, including BR, FS-DR, and LLSF. But, these methods are not as accurate as they could be. In this paper, a new multi-Label classification method is proposed based on graph representation. A feature selection technique and the Q-learning method are employed to increase the accuracy of the proposed algorithm. The proposed multi-Label classification algorithm is applied to various standard multi-Label datasets. The results are compared with state-of-the-art algorithms based on the well-known performance evaluation metrics. Experimental results demonstrated the effectiveness of the proposed model and its superiority over the other methods.